home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v17n04 / redblack.asc < prev    next >
Encoding:
Text File  |  1992-03-10  |  2.3 KB  |  90 lines
  1. _RED-BLACK TRESS_
  2. by Bruce Schneier
  3.  
  4. [Example 1: Insert operation, in pseudocode]
  5.  
  6.  
  7. RedBlackInsert(T,x)
  8. {
  9.     TreeInsert(T,x)
  10.     color(x) <-- Red
  11.     while x != root(T) and color(p(x))==Red
  12.         if p(x)==left(p(p(x)))
  13.             y <-- right(p(p(x)))
  14.             if color(y)==Red  
  15.                 color(p(x)) <-- Black
  16.                 color(y) <-- Black
  17.                 color(p(p(x))) <-- Red
  18.                 x <-- p(p(x))
  19.             else
  20.                 if x==right(p(x))
  21.                     x <-- p(x)
  22.                     RotateLeft(T,x)
  23.                 color(p(x)) <-- Black
  24.                 color(p(p(x))) <-- Red
  25.                 RotateRight(T, p(p(x)))
  26.         else
  27.             /* this is the same as the "then" clause,
  28.              * with "right" and "left" interchanged */
  29.     color(root(T)) <-- Black
  30. }
  31.  
  32.  
  33.  
  34. [Example 2: Delete operation, in pseudocode]
  35.  
  36. RedBlackDelete(T,z)
  37. {
  38.     if left(z)==nil(T) or right(z)==nil(T)
  39.         y <-- z
  40.     else
  41.         y <-- TreeSuccessor(z)
  42.     if left(y) != nil(T)
  43.         x <-- left(y)
  44.     else
  45.         x <-- right(y)
  46.     p(x) <-- p(y)
  47.     if p(y) == nil(T)
  48.        root(T) <-- x
  49.     else
  50.        if y==left(p(y))
  51.           left(p(x)) <-- x
  52.        else
  53.           right(p(y)) <-- x
  54.     if y != z
  55.        key(z) <-- key(y)
  56.        /* if y has other fields, copy them too */
  57.     if color(y)==Black
  58.        then RBDeleteFixup(T,x)
  59. }
  60. RBDeleteFixup(T,x)
  61. {
  62.      while x != root(T) and color(x)==Black
  63.         if x==left(p(x))
  64.             w <-- right(p(x))
  65.             if color(w) <-- Black
  66.                color(p(x)) <-- Red
  67.                RotateLeft(T,p(x))
  68.                w <-- right(p(x))
  69.             if color(left(w)) == Black and color(right(w))==Black
  70.                color(w) <-- Red
  71.                x <-- parent(x)
  72.             else 
  73.                if color(right(w)) == Black
  74.                   color(left(w)) <-- Black
  75.                   color(w) <-- Red
  76.                   RotateRight(T,w)
  77.                   w <-- right(p(x))
  78.                color(w) <-- color(p(x))
  79.                color(p(x)) <-- Black
  80.                color(right(w)) <-- Black
  81.                RotateLeft(T,p(x))
  82.                x <-- root(T)
  83.  
  84.          else
  85.             /* this is same as "then" clause,
  86.              * except that right and left are exchanged */
  87.      color(x) <--Black
  88. }
  89.  
  90.